package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 986. 区间列表的交集
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/13 21:30
 */
public class IntervalIntersection {


    public static void main(String[] args) {
        IntervalIntersection test = new IntervalIntersection();

        // [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
//        int[][] firstList = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
//        int[][] secondList = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};

        // {}
//        int[][] firstList ={{1,3},{5,9}};
//        int[][] secondList = {};

        // {}
//        int[][] firstList = {};
//        int[][] secondList = {{4,8},{10,12}};

        // {{3,7}}
        int[][] firstList = {{1, 7}};
        int[][] secondList = {{3, 10}};

        int[][] ints = test.intervalIntersection(firstList, secondList);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }

    }

    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<Long> list = new ArrayList<>();
        int a = firstList.length;
        int b = secondList.length;
        int i = 0;
        int j = 0;
        while (i < a && j < b) {
            int[] as = firstList[i];
            int[] bs = secondList[j];
            if (as[1] < bs[0]) {
                i++;
                continue;
            }
            if (bs[1] < as[0]) {
                j++;
                continue;
            }
            long m = ((long) Math.max(as[0], bs[0])) << 32;
            if (as[1] <= bs[1]) {
                i++;
                list.add(m + as[1]);
            } else {
                j++;
                list.add(m + bs[1]);
            }
        }
        int l = list.size();
        int[][] arr = new int[l][2];
        for (int k = 0; k < l; k++) {
            long v = list.get(k);
            arr[k][1] = (int) (0XFFFFFFFFL & v);
            arr[k][0] = (int) (v >> 32);
        }
        return arr;
    }

}
